#include<stdio.h>
#include<string.h>
int main()
{
    freopen("in.txt","r",stdin);
    char str[100][3];
    char str2[100][3];
    char temp[3];
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)  
    {
        scanf("%s",str[i]);
        strcpy(str2[i],str[i]);
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n-i-1; j++)
        {
            if(str[j][1] > str[j+1][1])
            {
                strcpy(temp,str[j]);
                strcpy(str[j],str[j+1]);
                strcpy(str[j+1],temp);
            }
        }
    }
    for(int i = 0; i < n; i++) printf("%s ",str[i]);
    printf("\nStable\n");
    for(int i = 0; i < n; i++)
    {
        int min = i;
        for(int j = i; j < n; j++)
        {
            if(str2[j][1] < str2[min][1]) min = j;
        }
        if(min != i)
        {
            strcpy(temp,str2[i]);
            strcpy(str2[i],str2[min]);
            strcpy(str2[min],temp);
        }
    }
    for(int i = 0; i < n; i++) printf("%s ",str2[i]);
    int flag = 1;
    for(int i = 0; i < n; i++)
    {
        if(str[i][0] != str2[i][0]) flag = 0;
    }
    if(flag) printf("\nStable");
    else printf("\nNot stable");
}